#include "internal.h"

#define __node_2_dle(node) \
    rb_entry((node), struct sched_dl_entity, rb_node)

static void update_curr_dl(struct rq *rq);
static int start_dl_timer(struct sched_dl_entity *dl_se);
static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
static void enqueue_dl_entity(struct sched_dl_entity *dl_se, int flags);

static bool dl_server(struct sched_dl_entity *dl_se)
{
    return dl_se->dl_server;
}

static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
{
    return container_of(dl_se, struct task_struct, dl);
}

static inline struct rq *rq_of_dl_se(struct sched_dl_entity *dl_se)
{
    struct rq *rq = dl_se->rq;

    if (!dl_server(dl_se))
        rq = task_rq(dl_task_of(dl_se));

    return rq;
}

static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
{
    return &rq_of_dl_se(dl_se)->dl;
}

static inline int on_dl_rq(struct sched_dl_entity *dl_se)
{
    return !RB_EMPTY_NODE(&dl_se->rb_node);
}

static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
{
    return container_of(dl_rq, struct rq, dl);
}

static inline bool __dl_less(struct rb_node *a, const struct rb_node *b)
{
    return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline);
}

static struct sched_dl_entity *pick_next_dl_entity(struct dl_rq *dl_rq)
{
    struct rb_node *left = rb_first_cached(&dl_rq->root);

    if (!left)
        return NULL;

    return __node_2_dle(left);
}

static inline struct sched_dl_entity *pi_of(struct sched_dl_entity *dl_se)
{
    return dl_se->pi_se;
}

static inline bool is_dl_boosted(struct sched_dl_entity *dl_se)
{
    return pi_of(dl_se) != dl_se;
}

static inline int is_leftmost(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
    return rb_first_cached(&dl_rq->root) == &dl_se->rb_node;
}

static int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
{
    return (dl_se->runtime <= 0);
}

/*
 * Regarding the deadline, a task with implicit deadline has a relative
 * deadline == relative period. A task with constrained deadline has a
 * relative deadline <= relative period.
 *
 * We support constrained deadline tasks. However, there are some restrictions
 * applied only for tasks which do not have an implicit deadline. See
 * update_dl_entity() to know more about such restrictions.
 *
 * The dl_is_implicit() returns true if the task has an implicit deadline.
 */
static inline bool dl_is_implicit(struct sched_dl_entity *dl_se)
{
	return dl_se->dl_deadline == dl_se->dl_period;
}

static inline u64 dl_next_period(struct sched_dl_entity *dl_se)
{
	return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
}

/*
 * Here we check if --at time t-- an entity (which is probably being
 * [re]activated or, in general, enqueued) can use its remaining runtime
 * and its current deadline _without_ exceeding the bandwidth it is
 * assigned (function returns true if it can't). We are in fact applying
 * one of the CBS rules: when a task wakes up, if the residual runtime
 * over residual deadline fits within the allocated bandwidth, then we
 * can keep the current (absolute) deadline and residual budget without
 * disrupting the schedulability of the system. Otherwise, we should
 * refill the runtime and set the deadline a period in the future,
 * because keeping the current (absolute) deadline of the task would
 * result in breaking guarantees promised to other tasks (refer to
 * Documentation/scheduler/sched-deadline.rst for more information).
 *
 * This function returns true if:
 *
 *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
 *
 * IOW we can't recycle current parameters.
 *
 * Notice that the bandwidth check is done against the deadline. For
 * task with deadline equal to period this is the same of using
 * dl_period instead of dl_deadline in the equation above.
 */
static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
{
    u64 left, right;

    /*
     * left and right are the two sides of the equation above,
     * after a bit of shuffling to use multiplications instead
     * of divisions.
     *
     * Note that none of the time values involved in the two
     * multiplications are absolute: dl_deadline and dl_runtime
     * are the relative deadline and the maximum runtime of each
     * instance, runtime is the runtime left for the last instance
     * and (deadline - t), since t is rq->clock, is the time left
     * to the (absolute) deadline. Even if overflowing the u64 type
     * is very unlikely to occur in both cases, here we scale down
     * as we want to avoid that risk at all. Scaling down by 10
     * means that we reduce granularity to 1us. We are fine with it,
     * since this is only a true/false check and, anyway, thinking
     * of anything below microseconds resolution is actually fiction
     * (but still we want to give the user that illusion >;).
     */
    left = (pi_of(dl_se)->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
    right = ((dl_se->deadline - t) >> DL_SCALE) *
            (pi_of(dl_se)->dl_runtime >> DL_SCALE);

    return dl_time_before(right, left);
}

static inline void inc_dl_tasks_cs(struct task_struct *task) {}
static inline void dec_dl_tasks_cs(struct task_struct *task) {}

#include "dl-scaled_delta_exec.c"
#include "dl-count_deadline.c"
#include "dl-bw.c"
#include "dl-wakeup_preempt.c"
#include "dl-server.c"
#include "dl-replenish.c"
#include "dl-timer.c"
#include "dl-pushable.c"
#include "dl-schedstat.c"
#include "dl-task_contending.c"
#include "dl-enqueue_task.c"
#include "dl-dequeue_task.c"
#include "dl-update_curr.c"
#include "dl-pick_task.c"
#include "dl-task_tick.c"
#include "dl-prio_changed.c"
#include "dl-switched_from.c"
#include "dl-switched_to.c"
#include "dl-set_next_task.c"
#include "dl-put_prev_task.c"

/*
 * This function clears the sched_dl_entity static params.
 */
static void __dl_clear_params(struct sched_dl_entity *dl_se)
{
    dl_se->dl_runtime = 0;
    dl_se->dl_deadline = 0;
    dl_se->dl_period = 0;
    dl_se->dl_bw = 0;

    dl_se->dl_throttled = 0;
    dl_se->dl_yielded = 0;
    dl_se->dl_non_contending = 0;
    dl_se->dl_overrun = 0;
    dl_se->dl_server = 0;
    dl_se->pi_se = dl_se;
}

static void init_dl_rq(struct rq *rq)
{
    struct dl_rq *dl_rq = &rq->dl;

    dl_rq->root = RB_ROOT_CACHED;
}

DEFINE_SCHED_CLASS(dl) = {
    .enqueue_task = enqueue_task_dl,
    .dequeue_task = dequeue_task_dl,

    .pick_task = pick_task_dl,
    .put_prev_task = put_prev_task_dl,
    .set_next_task = set_next_task_dl,

    .task_tick = task_tick_dl,

    .wakeup_preempt = wakeup_preempt_dl,

    .prio_changed = prio_changed_dl,
    .switched_from = switched_from_dl,
    .switched_to = switched_to_dl,

    .update_curr = update_curr_dl,

    .init_rq = init_dl_rq,
};

/*
 * Tells if entity @a should preempt entity @b.
 */
bool dl_entity_preempt(const struct sched_dl_entity *a,
                       const struct sched_dl_entity *b)
{
    return dl_time_before(a->deadline, b->deadline);
}

void init_dl_entity(struct task_struct *p)
{
    struct sched_dl_entity *dl_se = &p->dl;

    RB_CLEAR_NODE(&dl_se->rb_node);
    init_dl_task_timer(dl_se);
    init_dl_inactive_task_timer(dl_se);
    __dl_clear_params(dl_se);
}
